package Demo7;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三数之和
 * https://leetcode.cn/problems/3sum/description/
 * 1. 先排序
 * 2. 确定一个值 a 遍历数组
 * 采用双指针算法,查找到 l + r + a == 0 的时候  然后处理去重问题
 * 每次双指针结束后,处理 a 去重的问题
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 1.我们先进行排序
        Arrays.sort(nums);
        // 2. 利用双指针算法, 来实现这个方法
        List<List<Integer>> lists = new ArrayList<>();
        for(int i = nums.length - 1; i >= 2;i--) { // 遍历最大值
            int left = 0,right = i - 1;
            while(left < right) {
                // 使用双指针算法 计算 0 - i - 1 下标范围的值 和 i 下标相加的值
                int sum = nums[left] + nums[right] + nums[i];
                if(sum > 0) {
                    // 大于0 那right就得 --
                    right--;
                }else if(sum < 0) {
                    // 小于0 那left 就得++;
                    left++;
                }else {
                    // 等于0 那就需要放入到里链表当中
                    lists.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 我们这里的两个while 循环是用来去重 left 和right 的
                    while(left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                }
            }
            // 这里的while 循环是用来去重i的
            while(i > 0 && nums[i - 1] == nums[i]) {
                i--;
            }
            if(nums[i] <= 0) {
                break;
            }
        }
        return lists;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.threeSum(new int[] {-1,-2,-3,4,1,3,0,3,-2,1,-2,2,-1,1,-5,4,-3});
        for(List<Integer> list:lists) {
            System.out.println(list);
        }
    }
}